/**
 * All positive integers can be partitioned in such a way that each and every 
 * term of the partition can be expressed as (2^i)*(3^j), where i,j >= 0.
 *
 * Let's consider only those such partitions where none of the terms can divide 
 * any of the other terms. 
 *
 * For example, the partition of 17 = 2 + 6 + 9 = (2^1*3^0 + 2^1*3^1 + 2^0*3^2) 
 * would not be valid since 2 can divide 6. Neither would the partition 
 * 17 = 16 + 1 = (2^4*3^0 + 2^0*3^0) since 1 can divide 16. The only valid 
 * partition of 17 would be 8 + 9 = (2^3*3^0 + 2^0*3^2).
 *
 * Many integers have more than one valid partition, the first being 11 having 
 * the following two partitions. 
 *   11 = 2 + 9 = (2^1*3^0 + 2^0*3^2) 
 *   11 = 8 + 3 = (2^3*3^0 + 2^0*3^1)
 *
 * Let's define P(n) as the number of valid partitions of n. For example, 
 * P(11) = 2.
 *
 * Let's consider only the prime integers q which would have a single valid 
 * partition such as P(17).
 *
 * The sum of the primes q <= 100 such that P(q)=1 equals 233.
 *
 * Find the sum of the primes q <= 1000000 such that P(q)=1.
 *
 * Note: Others have faster implementation:
 * DP in C++. Store var[n][J] - number of valid partitions of n with all 
 * j <= J (n = sum 2^i*3^j). Runtime 15ms 
 * 
 * Let S(M) = sum of all prime q < M such P(q) = 1 
 * so S(10^6) = 3053105 (in 15 ms) 
 * S(10^7) = 27293596 (in 200 ms) 
 * S(10^8) = 513758825 (in 2.2 s) 
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include "euler/static.hpp"
#include "euler/prime_table.hpp"
#include "euler.h"

BEGIN_PROBLEM(333, solve_problem_333)
	PROBLEM_TITLE("Special partitions")
	PROBLEM_ANSWER("3053105")
	PROBLEM_DIFFICULTY(2)
	PROBLEM_FUN_LEVEL(2)
	PROBLEM_TIME_COMPLEXITY("")
	PROBLEM_SPACE_COMPLEXITY("")
END_PROBLEM()

#if 0
//static const int M = 99;
static const int M = 9999999;
#else
static const int M = 999999;
#endif

static const int LOG3M = euler::static_log<M,3>::value;

static int P[M+1][LOG3M+1];

/// @todo Improve the algorithm to match the performance of others.
static void solve_problem_333()
{
	// Boundary condition: P(0; J) = 1
	for (int J = 0; J <= LOG3M; J++)
	{
		P[0][J] = 1;
	}

	for (int n = 1; n <= M; n++)
	{
		if (n % 2 == 0) // n is even
		{
			for (int J = 0; J <= LOG3M; J++)
				P[n][J] = P[n/2][J];
		}
		else // n is odd
		{
			int J = 0, pow3J = 1;
			// J = 0
			P[n][0] = (n == 1)? 1 : 0;
			// J >= 1
			for (J = 1, pow3J = 3; pow3J <= n; ++J, pow3J *= 3)
			{
				P[n][J] = P[n][J-1] + P[n-pow3J][J-1];
			}
			// J > log3(n)
			for (; J <= LOG3M; ++J)
				P[n][J] = P[n][J-1];
		}
	}

	// Count primes q where P(q) == 1.
	int sum = 0;
	euler::prime_table<int> primes(M);
	for (auto it = primes.begin(); it != primes.end(); ++it)
	{
		int p = *it;
		if (P[p][LOG3M] == 1)
		{
			//std::cout << p << std::endl;
			sum += p;
		}
	}
	std::cout << sum << std::endl;
}
